package sort;

import java.util.Arrays;
import java.util.Base64;

public class Solution {
    public static void bubbleSort(int[] a, int n) {
        if (n <= 1) {
            return;
        }
        for (int i = 0; i < n; i++) {
            boolean flag = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    int tmp = a[j + 1];
                    a[j + 1] = a[j];
                    a[j] = tmp;
                    flag = true;
                }
            }
            if (!flag) break;
        }
    }


    public static void insertionSort(int[] a, int n) {
        if (n <= 1) {
            return;
        }
        for (int i = 1; i < n; i++) {
            int value = a[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (a[j] > value) {
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }
            a[j + 1] = value;
        }
    }

    public static void selectSort(int[] a, int n) {
        for (int i = 0; i < n; i++) {
            int min = i;
            for (int j = 1 + i; j < n; j++) {
                if (a[min] > a[j]) {
                    min = j;
                }
            }
            if (min != i) {
                int tmp = a[i];
                a[i] = a[min];
                a[min] = tmp;
            }
        }
    }

    public static void merge_sort(int[] a, int n){
        merge_sort_c(a,0,n-1);
    }
    public static void merge_sort_c(int[] a,int p,int r){
        if(p>=r){
            return;
        }
        int q=(p+r)/2;
        merge_sort_c(a,p,q);
        merge_sort_c(a,q+1,r);
        merge(a,p,q,r);
    }

    public static void merge(int[] a,int p,int q,int r){
        int  i=p;
        int j=q+1;
        int k=0;
        // 申请一个大小跟a[p...r]一样的临时数组
        int[] tem=new int[r-p+1];
        while (i<=q&&j<=r){
            if(a[i]<=a[j]){
                tem[k++]=a[i++];
            }else{
                tem[k++]=a[j++];
            }
        }
        // 判断哪个子数组中有剩余的数据
        int start=i;
        int end=q;
        if(j<=r){
            start=j;
            end=r;
        }

        // 将剩余的数据拷贝到临时数组tmp
        while (start<=end){
            tem[k++]=a[start++];
        }
        System.out.println(Arrays.toString(tem));
        // 将tmp中的数组拷贝回a[p...r]
        for (int m = 0; m <= r-p ; m++) {
            a[p+m]=tem[m];
        }
        System.out.println(Arrays.toString(a));
    }

    public static void main(String[] args) {
        int[] i = new int[]{10, 2, 3, 4, 55, 6, 8};
//        bubbleSort(i,7);
//        insertionSort(i, 7);
//        selectSort(i,7);
        merge_sort(i,7);
        System.out.println(Arrays.toString(i));
    }
}
